package class04;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.awt.*;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MyHeap2 {

    public static class MyMaxHeap{
        private int[] heap;
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit){
            heap=new int[limit];
            this.limit=limit;
            heapSize=0;
        }

        public boolean isEmpty(){
            return heapSize==0;
        }

        public boolean isFull(){
            return heapSize==limit;
        }

        public void push(int value){
            if (heapSize==limit)
                throw new RuntimeException("heap is full!");
            heap[heapSize]=value;
            heapInsert(heap,heapSize++);
        }

        public void heapInsert(int[] arr,int index){
            while (arr[index]>arr[(index-1)/2]){
                swap(heap,index,(index-1)/2);
                index=(index-1)/2;
            }
        }

        public void swap(int[] arr,int i,int j){
            int tmp = arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }

        public int pop(){
            int ans = heap[0];
            swap(heap,0,--heapSize);
            heapify(heap,0,heapSize);
            return ans;
        }

        public void heapify(int[] arr,int index,int heapSize){
            int left = index*2+1;
            while (left<heapSize){
                int largest = left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
                largest=arr[largest]>arr[index]?largest:index;
                if (largest==index)
                    break;
                swap(heap,largest,index);
                index = largest;
                left=index*2+1;
            }
        }
    }

    public static class RightMaxHeap{
        private int[] heap;
        private final int limit;
        private int heapSize;

        public RightMaxHeap(int limit){
            heap=new int[limit];
            this.limit=limit;
            heapSize=0;
        }

        public boolean isEmpty(){
            return heapSize==0;
        }

        public boolean isFull(){
            return heapSize==limit;
        }

        public void push(int value){
            if (heapSize==limit)
                throw new RuntimeException("heap is full!");
            heap[heapSize++]=value;
        }

        public int pop(){
            int maxIndex = 0;
            for (int i=0;i<heapSize;i++){
                if (heap[i]>heap[maxIndex])
                    maxIndex=i;
            }
            int ans = heap[maxIndex];
            heap[maxIndex]=heap[--heapSize];
            return ans;
        }
    }

    public static void main(String[] args) {



        int value = 1000;
        int limit = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1;
            MyMaxHeap my = new MyMaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Oops!");
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Oops!");
                }
                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) {
                    if (my.pop() != test.pop()) {
                        System.out.println("Oops!");
                    }
                } else {
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
        }
        System.out.println("finish!");

    }
}
